package com.chj.linkedlist;

public class Code06_SmallerEqualBigger {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node listPartition1(Node head, int pivot) {
		if (head == null) {
			return head;
		}
		Node cur = head;
		int len = 0;
		while (cur != null) {
			len++;
			cur = cur.next;
		}
		Node[] nodeArr = new Node[len];
		cur = head;
		for (int i = 0; i < len; i++) {
			nodeArr[i] = cur;
			cur = cur.next;
		}
		partition(nodeArr, 0, len - 1, pivot);
		for (int i = 1; i < len; i++) {
			nodeArr[i - 1].next = nodeArr[i];
		}
		nodeArr[len - 1].next = null;
		return nodeArr[0];
	}

	// 荷兰国旗问题
	public static int[] partition(Node[] arr, int L, int R, int p) {
		int less = L - 1; // <区的右边界
		int more = R + 1; // >区的左边界
		int index = L;
		while (index < more) { // L是当前数的下标
			if (arr[index].value < p) {
				less += 1;
				swap(arr, less, index);
				index += 1;
			} else if (arr[index].value > p) {
				more -= 1;
				swap(arr, more, index);
			} else {
				index += 1;
			}
		}
		return new int[] { less + 1, more - 1 };
	}

	public static void swap(Node[] arr, int i, int j) {
		Node tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

//	public static void arrPartition(Node[] nodeArr, int pivot) {
//		int small = -1;
//		int big = nodeArr.length;
//		int index = 0;
//		while (index != big) {
//			if (nodeArr[index].value < pivot) {
//				swap(nodeArr, ++small, index++);
//			} else if (nodeArr[index].value == pivot) {
//				index++;
//			} else {
//				swap(nodeArr, --big, index);
//			}
//		}
//	}
//
//	public static void swap(Node[] nodeArr, int a, int b) {
//		Node tmp = nodeArr[a];
//		nodeArr[a] = nodeArr[b];
//		nodeArr[b] = tmp;
//	}

	public static Node listPartition2(Node head, int pivot) {
		Node sH = null; // small head
		Node sT = null; // small tail
		Node eH = null; // equal head
		Node eT = null; // equal tail
		Node bH = null; // big head
		Node bT = null; // big tail
		Node next = null; // save next node
		// every node distributed to three lists
		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < pivot) {
				if (sH == null) {
					sH = head;
					sT = head;
				} else {
					sT.next = head;
					sT = head;
				}
			} else if (head.value == pivot) {
				if (eH == null) {
					eH = head;
					eT = head;
				} else {
					eT.next = head;
					eT = head;
				}
			} else {
				if (bH == null) {
					bH = head;
					bT = head;
				} else {
					bT.next = head;
					bT = head;
				}
			}
			head = next;
		}
		// small and equal reconnect
		if (sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		// all reconnect
		if (eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : eH != null ? eH : bH;
	}

	public static void printLinkedList(Node node) {
		System.out.print("Linked List: ");
		while (node != null) {
			System.out.print(node.value + " ");
			node = node.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head1 = new Node(7);
		head1.next = new Node(9);
		head1.next.next = new Node(1);
		head1.next.next.next = new Node(8);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(2);
		head1.next.next.next.next.next.next = new Node(5);
		printLinkedList(head1);
		head1 = listPartition1(head1, 5);
//		head1 = listPartition2(head1, 5);
		printLinkedList(head1);

	}

}
